Syntax10.Scn.Fnt
Syntax10b.Scn.Fnt
MODULE SortPlus;
IMPORT S:=SortBasics;
CONST N=150;
PROCEDURE InsertSort;
	VAR i, k, x, y: INTEGER;
	BEGIN
		FOR i:=1 TO N-1 DO
			S.Get(i, x); k:=i-1;
			LOOP
				S.Get(k, y); IF x >= y THEN EXIT END;
				S.Put(k+1, y);
				DEC(k); IF k=-1 THEN EXIT END
			END;
			S.Put(k+1, x)
		END;
		S.Done;
	END InsertSort;
PROCEDURE Insert*;
	BEGIN S.Install(InsertSort, N, "Insert") END Insert;
PROCEDURE BubbleSort;
		i, x, y: INTEGER;
		sorted: BOOLEAN;
	BEGIN
		REPEAT
			sorted:=TRUE;
			FOR i:=1 TO N-1 DO
				S.Get(i-1, x); S.Get(i, y);
				IF x>y THEN S.Put(i-1, y); S.Put(i, x); sorted:=FALSE END
			END
		UNTIL sorted;
		S.Done;
	END BubbleSort;
PROCEDURE Bubble*;
	BEGIN S.Install(BubbleSort, N, "Bubble") END Bubble;
PROCEDURE HeapSort;
	VAR l, r, elemL, elemR: INTEGER;
	PROCEDURE Sift;
		VAR l1, r1, x: INTEGER;
		BEGIN
			l1:=l; S.Get(l1, elemL);
			LOOP
				r1:=2*l1; IF r1 > r THEN EXIT END;
				S.Get(r1, elemR);
				IF r1 < r THEN
					S.Get(r1+1, x); IF elemR < x THEN elemR:=x; INC(r1) END;
				END;
				IF elemL >= elemR THEN EXIT END;
				S.Put(l1, elemR); l1:=r1
			END;
			S.Put(l1, elemL)
		END Sift;
	BEGIN
		l:=N DIV 2; r:=N-1;
		WHILE l>0 DO DEC(l); Sift END;
		WHILE r>0 DO
			S.Get(l, elemL); S.Get(r, elemR); S.Put(l, elemR); S.Put(r, elemL);
			DEC(r); Sift
		END;
		S.Done;
	END HeapSort;
PROCEDURE Heap*;
	BEGIN S.Install(HeapSort, N, "Heap") END Heap;
PROCEDURE QuickSort;
	PROCEDURE Q(l, r: INTEGER);
		VAR key, l1, r1, elemL, elemR: INTEGER;
		BEGIN
			S.Get(l, key);
			l1:=l; r1:=r;
			REPEAT
				LOOP S.Get(l1, elemL); IF elemL >= key THEN EXIT END; INC(l1) END;
				LOOP S.Get(r1, elemR); IF elemR <= key THEN EXIT END; DEC(r1) END;
				IF l1 <= r1 THEN
					S.Put(l1, elemR); S.Put(r1, elemL);
					INC(l1); DEC(r1)
				END
			UNTIL l1 > r1;
			IF l < r1 THEN Q(l, r1) END;
			IF l1 < r THEN Q(l1, r) END
		END Q;
	BEGIN
		Q(0, N-1);
		S.Done
	END QuickSort;
PROCEDURE Quick*;
	BEGIN S.Install(QuickSort, N, "Quick") END Quick;
PROCEDURE Start*;
	BEGIN S.Schedule END Start;
PROCEDURE Randomize*;
		i, r: INTEGER;
		data: S.Data;
	BEGIN
		data[0]:=0;
		FOR i:=1 TO N-1 DO r:=S.RND(i+1); data[i]:=data[r]; data[r]:=i END;
		S.NewData(data, N)
	END Randomize;
END SortPlus.